选择排序
选择排序的基本思想
选择排序算法的基本思想是通过选择和交换来实现排序：
（1）首先选取数组中最小的数据，将其和位于第一位的数据交换
（2）接着从剩下的 N-1 个数据中选择最小的数据，将其和位于第二位的数据交换
（3）重复上述步骤，直至最后两个数据交换完成
选择排序示例
以升序排序为例：从左向右排序，小的在左边，大的在右边
初始数据：[67, 55, 60, 45, 50]
一次排序：[45, 55, 60, 67, 50]
二次排序：[45, 50, 60, 67, 55]
三次排序：[45, 50, 55, 67, 60]
四次排序：[45, 50, 55, 60, 67]
排序结果：[45, 50, 55, 60, 67]
（1）一次排序：从原始数组中选择最小的数据 45，将其和第一个数据进行交换，交换后：[45, 55, 60, 67, 50]
（2）二次排序：从第二个数据开始，选择最小的数据 50，将其和第二个数据进行交换，交换后：[45, 50, 60, 67, 55]
（3）三次排序：从第三个数据开始，选择最小的数据 55，将其和第三个数据进行交换，交换后：[45, 50, 55, 67, 60]
（4）四次排序：从第四个数据开始，选择最小的数据 60，将其和第四个数据进行交换，交换后：[45, 50, 55, 60, 67]
选择升序排序：
1 | public static int[] selectAscSort(int[] arr) { |
插入降序排序：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public static int[] selectAscSort(int[] arr) {
int size = arr.length ;
int index;
int temp;
for(int i = 0; i < size - 1; i++) {
index = i;
for(int j = i+1; j < size; j++) {
if (arr[j] > arr[index]) {
index = j;
}
}
if (index != i) {
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
return arr;
}
插入排序
插入排序的基本思想
插入排序算法的基本思想是通过比较和插入来实现排序：
（1）首先对数组的前两个数据进行排序
（2）接着将第 3 个数据与已排好序的两个数据比较，将第 3 个数据插入合适的位置
（3）然后将第 4 个数据与已排好序的三个数据比较，将第 4 个数据插入合适的位置
（4）重复上述步骤，直至最后一个数据
插入排序示例
以升序排序为例：从左向右排序，小的在左边，大的在右边
初始数据：[67, 60, 55, 50, 45]
一次排序：[60, 67, 55, 50, 45]
二次排序：[55, 60, 67, 50, 45]
三次排序：[50, 55, 60, 67, 45]
四次排序：[45, 50, 55, 60, 67]
排序结果：[45, 50, 55, 60, 67]
（1）一次排序：对前两个数据进行排序
比较 67 和 60 ，由于 67 比 60 大，两者交换数据，交换位置后：[60, 67, 55, 50, 45]
（2）二次排序：取第三个数据和已排序好的前两个数据进行比较
首先将第三个数据和第二个数据比较，55 比 67 小，将 67 移动到第三个位置
继续将原第三个数据和第一个数据比较，55 比 60 小，将 60 移动到第二个位置
将原第三个数据放入第一个位置，最终数据：[55, 60, 67, 50, 45]
（3）三次排序：取第四个数据和已排序好的前三个数据进行比较
参考第二步
（4）四次排序：取第五个数据和已排序好的前四个数据进行比较
参考第三步
插入升序排序：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public static int[] insertAscSort(int[] arr) {
int size = arr.length;
int temp;
int j;
// 从第二位开始循环
for (int i = 1; i < size; i++) {
// 暂存当前循环开始位置的数据
temp = arr[i];
// 获取前一位位置
j = i-1;
while (j >= 0 && temp < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
return arr;
}
插入降序排序：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public static int[] insertAscSort(int[] arr) {
int size = arr.length;
int temp;
int j;
// 从第二位开始循环
for (int i = 1; i < size; i++) {
// 暂存当前循环开始位置的数据
temp = arr[i];
// 获取前一位位置
j = i-1;
while (j >= 0 && temp > arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
return arr;
}